
/*
 * @lc app=leetcode.cn id=221 lang=cpp
 *
 * [221] 最大正方形
 *
 * https://leetcode-cn.com/problems/maximal-square/description/
 *
 * algorithms
 * Medium (48.73%)
 * Likes:    1120
 * Dislikes: 0
 * Total Accepted:    189.4K
 * Total Submissions: 388.4K
 * Testcase Example:  '[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]'
 *
 * 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：matrix =
 * [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
 * 输出：4
 *
 *
 * 示例 2：
 *
 *
 * 输入：matrix = [["0","1"],["1","0"]]
 * 输出：1
 *
 *
 * 示例 3：
 *
 *
 * 输入：matrix = [["0"]]
 * 输出：0
 *
 *
 *
 *
 * 提示：
 *
 *
 * m == matrix.length
 * n == matrix[i].length
 * 1
 * matrix[i][j] 为 '0' 或 '1'
 *
 *
 */

// @lc code=start
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int maximalSquare(vector<vector<char>> &matrix) {
        int m = matrix.size();
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].size();
        // dp存储以当前下标为右下角的正方形的边长
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        int ans = 0;
        // 自己写的
        /* for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] - '0' == 0) {
                    dp[i + 1][j + 1] = 0;
                }
                else {
                    if (dp[i][j] == 0) {
                        dp[i + 1][j + 1] = 1;
                        ans = max(ans, dp[i + 1][j + 1]);
                    }
                    else {
                        dp[i + 1][j + 1] = 1;
                        int x = 1;

                        while (x <= dp[i][j]) {
                            if ((matrix[i - x][j] - '0') && (matrix[i][j - x] - '0')) {
                                ++dp[i + 1][j + 1];
                                ++x;
                            }
                            else {
                                break;
                            }
                        }
                        ans = max(ans, dp[i + 1][j + 1]);
                    }
                }
            }
        } */

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;
                }
                ans = max(ans, dp[i][j]);
            }
        }
        return ans * ans;
    }
};
// @lc code=end
